1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for sensor network routing.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the devices. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
There exists a class of networks in which a huge number of sources of data, referred to herein as sensors, may be distributed in an ad-hoc fashion. The sensors may be configured to generate, monitor, or capture many types of data, such as information related to temperature, position, RF-ID presence, water level, stress, light level, machine status, and numerous other types of data. The sensors, in addition to producing data, may also act as wireless transmit devices to transmit data from other sensors to allow the data to be received at a collection point. Generally, traffic patterns in such a network will tend to be very focused and will flow either from a well known focal point out to the other nodes, or the reverse, from all those nodes back to the focal point. In these networks rarely, if ever, does traffic flow in any other pattern.
FIGS. 1A-1E illustrate a network 10 in which a collector 12 is configured to collect information from a plurality of sensors 14 and to communicate with sensors in its vicinity. As shown in FIGS. 1A-1E, data from the sensors is communicated via other sensors to the collector to enable the collector to obtain data from various points of interest in the network.
FIGS. 1A-1E illustrate a sensor network in which all sensors are configured to transmit all data packets received. As shown in FIGS. 1A-1E, a message originating at a sensor 14 will be received by its neighbors. The neighbors (FIG. 1B) will also transmit the message in a pattern resembling a wave emanating through the network (FIGS. 1C-1E). Eventually, multiple copies of the message will arrive at one or more collectors 12 (FIG. 1E). While this presents a viable manner to transmit information reliably through the network, it causes excessive replication of messages which can cause congestion on the network and waste resources of the sensors on the network.
Sensors on the network typically have limited resources such as limited power, memory, transmission and processing capacity, and hence minimizing the number of transmissions on a sensor network is desirable. One way to do this is to introduce a notion of routing, which may be used to cause transmissions to propagate along paths in the sensor network. The broadcast nature of the transmissions emanating from the sensors as well as several other features of the sensor network, such as the fact that the sensors may be mobile and may be distributed in an ad-hoc nature, render most of the available routing techniques inapplicable. Additionally, several of the traditional network routing techniques require the transmission of routing updates between sensors, which themselves may deplete performance of the network and may not be able to be implemented given the limited resources of the sensors.